package 左哥算法.ch07图;

import org.junit.Test;

import java.util.*;

public class 最短路径方案数 {

    public static void main(String[] args) {
        PriorityQueue<Node> queue=new PriorityQueue<>((o1, o2) -> o1.id-o2.id);
        Node node = new Node(10);
        node.time=-111;
        Node node1 = new Node(2);
        Node n3=new Node(5);
        queue.add(node);
        queue.add(node1);
        queue.add(n3);
        node.id=0;
        queue.add(new Node(0));
        System.out.println(queue.peek());
    }

    /**
     * 最短路径方案数
     */
    @Test
    public void ch01() {
        int n = 5;
        int[][] roads = {
                {0, 1, 1}, {1, 2, 4}, {0, 4, 3}, {3, 2, 5}, {3, 4, 1}, {3, 0, 5}, {1, 3, 1},
        };
        int i = countPaths(n, roads);
        System.out.println(i);
    }

    /**
     * 最短路径方案数
     * @param n 节点个数
     * @param roads 边
     * @return 最短路径方案数
     */
    public int countPaths(int n, int[][] roads) {
        Graph graph = new Graph(n, roads);  // 构建图
        PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);  //优先队列用于存储节点到起点的最短距离和id
        boolean vis[] = new boolean[n];  // 记录节点是否已访问
        Node start = graph.map.get(0);  // 获取起始节点
        start.time = 0;  // 初始化起始节点的到达时间
        start.path = 1;  // 初始化起始节点的路径数
        int[] info={0,0};  // 起点的最短路径信息
        queue.add(info);  // 将起点的最短路径信息加入优先队列
        while (!queue.isEmpty()) {  // 当优先队列不为空时循环
            info = queue.poll();  // 弹出优先队列中的节点最短路径信息
            if (vis[info[0]]) continue;  // 如果节点已访问，则跳过
            vis[info[0]] = true;  // 将节点标记为已访问
            if (info[0] == n - 1) {  // 如果当前节点是终点节点，则返回最短路径方案数
                return graph.map.get(info[0]).path;
            }
            Node curr = graph.map.get(info[0]);  // 获取当前节点
            for (Edge edge : curr.edges) {  // 遍历当前节点的邻接边
                Node to = edge.to;  // 获取邻接节点
                if (vis[to.id]) continue;  // 如果邻接节点已访问，则跳过
                if (to.time == curr.time + edge.time) {  // 如果邻接节点的到达时间与当前节点到达邻接节点的花费时间相等，则更新路径数
                    to.path += curr.path;
                    to.path %= 1000000007;
                    continue;
                }
                if (to.time > curr.time + edge.time) {  // 如果邻接节点的到达时间大于当前节点到达邻接节点的花费时间，则更新到达时间和服务节点，并将邻接节点添加到优先队列中
                    to.time = curr.time + edge.time;
                    to.path = curr.path;
                    queue.add(new int[]{to.id, to.time});
                }
            }
        }
        return 0;  // 如果未找到最短路径方案数，则返回0
    }


    static class Graph {
        Map<Integer, Node> map = new HashMap<>();

        public Graph(int n, int[][] roads) {
            for (int i = 0; i < n; i++) {
                map.put(i, new Node(i));
            }
            for (int[] road : roads) {
                Node from = map.get(road[0]);
                Node to = map.get(road[1]);
                from.edges.add(new Edge(from, to, road[2]));
                to.edges.add(new Edge(to, from, road[2]));
            }
        }
    }

    static class Node {
        @Override
        public String toString() {
            return "Node{" +
                    "id=" + id +
                    ", time=" + time +
                    ", path=" + path +
                    '}';
        }

        int id;
        int time = Integer.MAX_VALUE;
        int path = 0;
        List<Edge> edges = new LinkedList<>();

        public Node(int id) {
            this.id = id;
        }
    }

    static class Edge {
        Node from;
        Node to;
        int time;

        public Edge(Node from, Node to, int time) {
            this.from = from;
            this.to = to;
            this.time = time;
        }
    }
}
